/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhongfang
 *
 */
public class MaximumWidthofBinaryTree {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	/**
	 * BFS
	 * @param root
	 * @return
	 */
	int max=0;
	public int widthOfBinaryTree2(TreeNode root) {
		help(root,0,1,new ArrayList<Integer>());
		return max;
	}
	private void help(TreeNode root, int depth, int id, ArrayList<Integer> arrayList) {
		if(root==null){
			return;
		}
		if(arrayList.size()<=depth){//记录最左侧id，即这一层的最小id
			arrayList.add(depth, id);
			max=Math.max(max, 1);
		}else {
			if(arrayList.get(depth)>id){
				arrayList.set(depth, id);
			}else {
				max=Math.max(max, id-arrayList.get(depth)+1);
			}
		}
		help(root.left, depth+1, 2*id, arrayList);
		help(root.right, depth+1, 2*id+1, arrayList);
	}
	/*
	 * out of memory
	 */
    public static int widthOfBinaryTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        Queue<TreeNode> queue2=new LinkedList<>();
        Queue<TreeNode>[] queues=new Queue[2];
        queues[0]=queue;
        queues[1]=queue2;
        int outQueIndex=1;
        int width=0;
        int maxWidth=0;
        while (width!=-1) {
        	int left=-1,right=-1;
        	int i=0;
        	int inQueIndex=outQueIndex;
        	outQueIndex=1-outQueIndex;
            while (!queues[outQueIndex].isEmpty()) {
            	i++;
    			TreeNode node=queues[outQueIndex].poll();
    			if(node==null){
    				if(left!=-1){//只需要加两个中间的
	    				queues[inQueIndex].add(null);
	    				queues[inQueIndex].add(null);
    				}
    			}else {
    				if(left==-1){
    					left=i;
    				}else {
						right=i;
					}
    				queues[inQueIndex].add(node.left);
    				queues[inQueIndex].add(node.right);
    			}
    		}
            if(left==-1){
            	width=-1;
            }else if (right==-1) {//只有一个非null节点
				width=1;
			}else {
            	width=right-left+1;
			}
        	maxWidth=Math.max(maxWidth, width);
		}
        return maxWidth;
    }
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode treeNode1=new TreeNode(1);
		TreeNode treeNode2=new TreeNode(3);
		TreeNode treeNode3=new TreeNode(2);
		TreeNode treeNode4=new TreeNode(5);
		TreeNode treeNode5=new TreeNode(3);
		TreeNode treeNode6=new TreeNode(9);
		treeNode1.left=treeNode2;
		treeNode1.right=treeNode3;
		treeNode2.left=treeNode4;
		treeNode2.right=treeNode5;
		treeNode3.right=treeNode6;
		System.out.println(new MaximumWidthofBinaryTree().widthOfBinaryTree2(treeNode6));
	}

}
